package _树;

import java.util.*;

public class BST {
    // 94 BST的迭代遍历:https://leetcode.cn/problems/binary-tree-inorder-traversal/
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        // 遍历的顺序和访问的顺序不一样，需要一个指针来指向当前节点
        if (root == null) return res;
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            // 叶子节点会两次判空，第一次判空弹出叶子节点，第二次判空弹出根节点
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }

    // 897：递增顺序搜索树：https://leetcode.cn/problems/increasing-order-search-tree/
    // 一般来说，直接对原链表进行操作，都需要新建一个 虚拟头节点
    public TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        TreeNode dummpy = new TreeNode(-1), pre = dummpy, cur = root;
        while (!st.isEmpty() || cur != null) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();

                pre.right = cur;
                cur.left = null;
                pre = cur;

                cur = cur.right;
            }
        }
        return dummpy.right;
    }

    // 938：BST的范围和：https://leetcode.cn/problems/range-sum-of-bst/
    public int rangeSumBST(TreeNode root, int low, int high) {
        Stack<TreeNode> st = new Stack<>();
        int sum = 0;
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                if (cur.val >= low && cur.val <= high) {
                    sum += cur.val;
                }
                cur = cur.right;
            }
        }
        return sum;
    }

    // 98：判断给定的树是不是BST
    // 利用中序遍历是有序的，这个特征，在迭代时进行判断
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        if (root == null) return true;
        TreeNode pre = null, cur = root;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                if (pre != null && pre.val >= cur.val) return false;
                pre = cur;
                cur = cur.right;
            }
        }
        return true;
    }

    // BST的最近公共祖先
    // 利用 BST 有序的性质
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = root;
        // 违反了 BST 性质的那个节点
        while (res != null) {
            if (p.val < res.val && q.val < res.val) {
                res = res.left;
            } else if (p.val > res.val && q.val > res.val) {
                res = res.right;
            } else
                break;
        }
        return res;
    }

    //  ：迭代法的中序遍历解决大部分题目
    // LCR：174：BST中的第k大的元素，反中序遍历

    // 230 :BST中的第k小的元素
    public int kthSmallest(TreeNode root, int k) {
        int count = 0;
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                count++;
                if (count == k) return cur.val;
                cur = cur.right;
            }
        }
        return 0;
    }

    // 501:BST中的众数
    public int[] findMode(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();

        int count = 0;//记录当前数的出现次数
        int countMax = 0; //记录众数的出现次数
        // 中序
        if (root == null) return null;
        TreeNode pre = null, cur = root;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                // 相等 计数；否则重新计数
                if (pre == null) count = 1;
                else if (pre.val == cur.val) count++;
                else count = 1;
                pre = cur;
                if (count > countMax) {
                    countMax = count;
                    res.clear();
                }
                // 第二个众数来了
                if (count == countMax) {
                    res.add(cur.val);
                }

                cur = cur.right;
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    //LCR 054:把二叉搜索树转换为累加树  https://leetcode.cn/problems/w6cpku/description/
    public TreeNode convertBST(TreeNode root) {
        //反中序遍历
        Stack<TreeNode> st = new Stack<>();
        int sum = 0;
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.right;
            } else {
                cur = st.pop();
                sum += cur.val;
                cur.val = sum;
                cur = cur.left;
            }
        }
        return root;
    }

    // 108 : 有序数组转 BST
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int rootIndex = (r - l) / 2 + l;
        // 把下一层的返回结果用当前层的 left / right 接住
        return new TreeNode(nums[rootIndex],
                build(nums, l, rootIndex - 1),
                build(nums, rootIndex + 1, r));
    }

    // 有序链表转 BST（直接在链表上操作）
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);

        return new TreeNode(mid.val, buildTree(left, mid), buildTree(mid.next, right));
    }

    // 快慢指针 找 链表的中间节点
    public ListNode getMedian(ListNode l, ListNode r) {
        ListNode f = l;
        ListNode s = l;
        while (f != r && f.next != r) {
            s = s.next;
            f = f.next.next;
        }
        return s;
    }

    // 1008：前序遍历构造 BST：[8,5,1,7,10,12]
    // https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/
    //  根据左右区间构造 BST
    public TreeNode bstFromPreorder(int[] preorder) {
        int n = preorder.length;
        if (n == 0) return null;
        return dfs(preorder, 0, n - 1);
    }

    // 根据左右区间构造 BST
    private TreeNode dfs(int[] preorder, int left, int right) {
        if (left > right)
            return null;
        TreeNode root = new TreeNode(preorder[left]);
        // [8,5,1,7,10,12]      找到 10
        int i = left + 1;
        for (; i <= right; i++) {
            if (preorder[i] > root.val)
                break;
        }
        root.left = dfs(preorder, left + 1, i - 1);
        root.right = dfs(preorder, i, right);
        return root;
    }

}

















